/**
 * sifter.js
 * Copyright (c) 2013 Brian Reavis & contributors
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this
 * file except in compliance with the License. You may obtain a copy of the License at:
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under
 * the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF
 * ANY KIND, either express or implied. See the License for the specific language
 * governing permissions and limitations under the License.
 *
 * @author Brian Reavis <brian@thirdroute.com>
 */

/**
 * Textually searches arrays and hashes of objects
 * by property (or multiple properties). Designed
 * specifically for autocomplete.
 *
 * @constructor
 * @param {array|object} items
 * @param {object} items
 */
var Sifter = function(items, settings) {
  this.items = items;
  this.settings = settings || {diacritics: true};
};

/**
 * Splits a search string into an array of individual
 * regexps to be used to match results.
 *
 * @param {string} query
 * @returns {array}
 */
Sifter.prototype.tokenize = function(query) {
  query = trim(String(query || '').toLowerCase());
  if (!query || !query.length) return [];

  var i, n, regex, letter;
  var tokens = [];
  var words = query.split(/ +/);

  for (i = 0, n = words.length; i < n; i++) {
    regex = escape_regex(words[i]);
    if (this.settings.diacritics) {
      for (letter in DIACRITICS) {
        if (DIACRITICS.hasOwnProperty(letter)) {
          regex = regex.replace(new RegExp(letter, 'g'), DIACRITICS[letter]);
        }
      }
    }
    tokens.push({
      string : words[i],
      regex  : new RegExp(regex, 'i')
    });
  }

  return tokens;
};

/**
 * Iterates over arrays and hashes.
 *
 * ```
 * this.iterator(this.items, function(item, id) {
 *    // invoked for each item
 * });
 * ```
 *
 * @param {array|object} object
 */
Sifter.prototype.iterator = function(object, callback) {
  var iterator;
  if (is_array(object)) {
    iterator = Array.prototype.forEach || function(callback) {
      for (var i = 0, n = this.length; i < n; i++) {
        callback(this[i], i, this);
      }
    };
  } else {
    iterator = function(callback) {
      for (var key in this) {
        if (this.hasOwnProperty(key)) {
          callback(this[key], key, this);
        }
      }
    };
  }

  iterator.apply(object, [callback]);
};

/**
 * Returns a function to be used to score individual results.
 *
 * Good matches will have a higher score than poor matches.
 * If an item is not a match, 0 will be returned by the function.
 *
 * @param {object|string} search
 * @param {object} options (optional)
 * @returns {function}
 */
Sifter.prototype.getScoreFunction = function(search, options) {
  var self, fields, tokens, token_count;

  self        = this;
  search      = self.prepareSearch(search, options);
  tokens      = search.tokens;
  fields      = search.options.fields;
  token_count = tokens.length;

  /**
   * Calculates how close of a match the
   * given value is against a search token.
   *
   * @param {mixed} value
   * @param {object} token
   * @return {number}
   */
  var scoreValue = function(value, token) {
    var score, pos;

    if (!value) return 0;
    value = String(value || '');
    pos = value.search(token.regex);
    if (pos === -1) return 0;
    score = token.string.length / value.length;
    if (pos === 0) score += 0.5;
    return score;
  };

  /**
   * Calculates the score of an object
   * against the search query.
   *
   * @param {object} token
   * @param {object} data
   * @return {number}
   */
  var scoreObject = (function() {
    var field_count = fields.length;
    if (!field_count) {
      return function() { return 0; };
    }
    if (field_count === 1) {
      return function(token, data) {
        return scoreValue(data[fields[0]], token);
      };
    }
    return function(token, data) {
      for (var i = 0, sum = 0; i < field_count; i++) {
        sum += scoreValue(data[fields[i]], token);
      }
      return sum / field_count;
    };
  })();

  if (!token_count) {
    return function() { return 0; };
  }
  if (token_count === 1) {
    return function(data) {
      return scoreObject(tokens[0], data);
    };
  }

  if (search.options.conjunction === 'and') {
    return function(data) {
      var score;
      for (var i = 0, sum = 0; i < token_count; i++) {
        score = scoreObject(tokens[i], data);
        if (score <= 0) return 0;
        sum += score;
      }
      return sum / token_count;
    };
  } else {
    return function(data) {
      for (var i = 0, sum = 0; i < token_count; i++) {
        sum += scoreObject(tokens[i], data);
      }
      return sum / token_count;
    };
  }
};

/**
 * Returns a function that can be used to compare two
 * results, for sorting purposes. If no sorting should
 * be performed, `null` will be returned.
 *
 * @param {string|object} search
 * @param {object} options
 * @return function(a,b)
 */
Sifter.prototype.getSortFunction = function(search, options) {
  var i, n, self, field, fields, fields_count, multiplier, multipliers, get_field, implicit_score, sort;

  self   = this;
  search = self.prepareSearch(search, options);
  sort   = (!search.query && options.sort_empty) || options.sort;

  /**
   * Fetches the specified sort field value
   * from a search result item.
   *
   * @param  {string} name
   * @param  {object} result
   * @return {mixed}
   */
  get_field  = function(name, result) {
    if (name === '$score') return result.score;
    return self.items[result.id][name];
  };

  // parse options
  fields = [];
  if (sort) {
    for (i = 0, n = sort.length; i < n; i++) {
      if (search.query || sort[i].field !== '$score') {
        fields.push(sort[i]);
      }
    }
  }

  // the "$score" field is implied to be the primary
  // sort field, unless it's manually specified
  if (search.query) {
    implicit_score = true;
    for (i = 0, n = fields.length; i < n; i++) {
      if (fields[i].field === '$score') {
        implicit_score = false;
        break;
      }
    }
    if (implicit_score) {
      fields.unshift({field: '$score', direction: 'desc'});
    }
  } else {
    for (i = 0, n = fields.length; i < n; i++) {
      if (fields[i].field === '$score') {
        fields.splice(i, 1);
        break;
      }
    }
  }

  multipliers = [];
  for (i = 0, n = fields.length; i < n; i++) {
    multipliers.push(fields[i].direction === 'desc' ? -1 : 1);
  }

  // build function
  fields_count = fields.length;
  if (!fields_count) {
    return null;
  } else if (fields_count === 1) {
    field = fields[0].field;
    multiplier = multipliers[0];
    return function(a, b) {
      return multiplier * cmp(
        get_field(field, a),
        get_field(field, b)
      );
    };
  } else {
    return function(a, b) {
      var i, result, a_value, b_value, field;
      for (i = 0; i < fields_count; i++) {
        field = fields[i].field;
        result = multipliers[i] * cmp(
          get_field(field, a),
          get_field(field, b)
        );
        if (result) return result;
      }
      return 0;
    };
  }
};

/**
 * Parses a search query and returns an object
 * with tokens and fields ready to be populated
 * with results.
 *
 * @param {string} query
 * @param {object} options
 * @returns {object}
 */
Sifter.prototype.prepareSearch = function(query, options) {
  if (typeof query === 'object') return query;

  options = extend({}, options);

  var option_fields     = options.fields;
  var option_sort       = options.sort;
  var option_sort_empty = options.sort_empty;

  if (option_fields && !is_array(option_fields)) options.fields = [option_fields];
  if (option_sort && !is_array(option_sort)) options.sort = [option_sort];
  if (option_sort_empty && !is_array(option_sort_empty)) options.sort_empty = [option_sort_empty];

  return {
    options : options,
    query   : String(query || '').toLowerCase(),
    tokens  : this.tokenize(query),
    total   : 0,
    items   : []
  };
};

/**
 * Searches through all items and returns a sorted array of matches.
 *
 * The `options` parameter can contain:
 *
 *   - fields {string|array}
 *   - sort {array}
 *   - score {function}
 *   - filter {bool}
 *   - limit {integer}
 *
 * Returns an object containing:
 *
 *   - options {object}
 *   - query {string}
 *   - tokens {array}
 *   - total {int}
 *   - items {array}
 *
 * @param {string} query
 * @param {object} options
 * @returns {object}
 */
Sifter.prototype.search = function(query, options) {
  var self = this, value, score, search, calculateScore;
  var fn_sort;
  var fn_score;

  search  = this.prepareSearch(query, options);
  options = search.options;
  query   = search.query;

  // generate result scoring function
  fn_score = options.score || self.getScoreFunction(search);

  // perform search and sort
  if (query.length) {
    self.iterator(self.items, function(item, id) {
      score = fn_score(item);
      if (options.filter === false || score > 0) {
        search.items.push({'score': score, 'id': id});
      }
    });
  } else {
    self.iterator(self.items, function(item, id) {
      search.items.push({'score': 1, 'id': id});
    });
  }

  fn_sort = self.getSortFunction(search, options);
  if (fn_sort) search.items.sort(fn_sort);

  // apply limits
  search.total = search.items.length;
  if (typeof options.limit === 'number') {
    search.items = search.items.slice(0, options.limit);
  }

  return search;
};

// utilities
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

var cmp = function(a, b) {
  if (typeof a === 'number' && typeof b === 'number') {
    return a > b ? 1 : (a < b ? -1 : 0);
  }
  a = String(a || '').toLowerCase();
  b = String(b || '').toLowerCase();
  if (a > b) return 1;
  if (b > a) return -1;
  return 0;
};

var extend = function(a, b) {
  var i, n, k, object;
  for (i = 1, n = arguments.length; i < n; i++) {
    object = arguments[i];
    if (!object) continue;
    for (k in object) {
      if (object.hasOwnProperty(k)) {
        a[k] = object[k];
      }
    }
  }
  return a;
};

var trim = function(str) {
  return (str + '').replace(/^\s+|\s+$|/g, '');
};

var escape_regex = function(str) {
  return (str + '').replace(/([.?*+^$[\]\\(){}|-])/g, '\\$1');
};

var is_array = Array.isArray || ($ && $.isArray) || function(object) {
  return Object.prototype.toString.call(object) === '[object Array]';
};

var DIACRITICS = {
  'a': '[aÀÁÂÃÄÅàáâãäå]',
  'c': '[cÇçćĆčČ]',
  'd': '[dđĐ]',
  'e': '[eÈÉÊËèéêë]',
  'i': '[iÌÍÎÏìíîï]',
  'n': '[nÑñ]',
  'o': '[oÒÓÔÕÕÖØòóôõöø]',
  's': '[sŠš]',
  'u': '[uÙÚÛÜùúûü]',
  'y': '[yŸÿý]',
  'z': '[zŽž]'
};

  // export
  // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -


/**
 * microplugin.js
 * Copyright (c) 2013 Brian Reavis & contributors
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this
 * file except in compliance with the License. You may obtain a copy of the License at:
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under
 * the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF
 * ANY KIND, either express or implied. See the License for the specific language
 * governing permissions and limitations under the License.
 *
 * @author Brian Reavis <brian@thirdroute.com>
 */

var MicroPlugin = {};

MicroPlugin.mixin = function(Interface) {
  Interface.plugins = {};

  /**
   * Initializes the listed plugins (with options).
   * Acceptable formats:
   *
   * List (without options):
   *   ['a', 'b', 'c']
   *
   * List (with options):
   *   [{'name': 'a', options: {}}, {'name': 'b', options: {}}]
   *
   * Hash (with options):
   *   {'a': { ... }, 'b': { ... }, 'c': { ... }}
   *
   * @param {mixed} plugins
   */
  Interface.prototype.initializePlugins = function(plugins) {
    var i, n, key;
    var self  = this;
    var queue = [];

    self.plugins = {
      names     : [],
      settings  : {},
      requested : {},
      loaded    : {}
    };

    if (utils.isArray(plugins)) {
      for (i = 0, n = plugins.length; i < n; i++) {
        if (typeof plugins[i] === 'string') {
          queue.push(plugins[i]);
        } else {
          self.plugins.settings[plugins[i].name] = plugins[i].options;
          queue.push(plugins[i].name);
        }
      }
    } else if (plugins) {
      for (key in plugins) {
        if (plugins.hasOwnProperty(key)) {
          self.plugins.settings[key] = plugins[key];
          queue.push(key);
        }
      }
    }

    while (queue.length) {
      self.require(queue.shift());
    }
  };

  Interface.prototype.loadPlugin = function(name) {
    var self    = this;
    var plugins = self.plugins;
    var plugin  = Interface.plugins[name];

    if (!Interface.plugins.hasOwnProperty(name)) {
      throw new Error('Unable to find "' +  name + '" plugin');
    }

    plugins.requested[name] = true;
    plugins.loaded[name] = plugin.fn.apply(self, [self.plugins.settings[name] || {}]);
    plugins.names.push(name);
  };

  /**
   * Initializes a plugin.
   *
   * @param {string} name
   */
  Interface.prototype.require = function(name) {
    var self = this;
    var plugins = self.plugins;

    if (!self.plugins.loaded.hasOwnProperty(name)) {
      if (plugins.requested[name]) {
        throw new Error('Plugin has circular dependency ("' + name + '")');
      }
      self.loadPlugin(name);
    }

    return plugins.loaded[name];
  };

  /**
   * Registers a plugin.
   *
   * @param {string} name
   * @param {function} fn
   */
  Interface.define = function(name, fn) {
    Interface.plugins[name] = {
      'name' : name,
      'fn'   : fn
    };
  };
};

var utils = {
  isArray: Array.isArray || function(vArg) {
    return Object.prototype.toString.call(vArg) === '[object Array]';
  }
};


/**
 * selectize.js (v0.8.5)
 * Copyright (c) 2013 Brian Reavis & contributors
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this
 * file except in compliance with the License. You may obtain a copy of the License at:
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under
 * the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF
 * ANY KIND, either express or implied. See the License for the specific language
 * governing permissions and limitations under the License.
 *
 * @author Brian Reavis <brian@thirdroute.com>
 */

/*jshint curly:false */
/*jshint browser:true */

var highlight = function($element, pattern) {
  if (typeof pattern === 'string' && !pattern.length) return;
  var regex = (typeof pattern === 'string') ? new RegExp(pattern, 'i') : pattern;

  var highlight = function(node) {
    var skip = 0;
    if (node.nodeType === 3) {
      var pos = node.data.search(regex);
      if (pos >= 0 && node.data.length > 0) {
        var match = node.data.match(regex);
        var spannode = document.createElement('span');
        spannode.className = 'highlight';
        var middlebit = node.splitText(pos);
        var endbit = middlebit.splitText(match[0].length);
        var middleclone = middlebit.cloneNode(true);
        spannode.appendChild(middleclone);
        middlebit.parentNode.replaceChild(spannode, middlebit);
        skip = 1;
      }
    } else if (node.nodeType === 1 && node.childNodes && !/(script|style)/i.test(node.tagName)) {
      for (var i = 0; i < node.childNodes.length; ++i) {
        i += highlight(node.childNodes[i]);
      }
    }
    return skip;
  };

  return $element.each(function() {
    highlight(this);
  });
};

var MicroEvent = function() {};
MicroEvent.prototype = {
  on: function(event, fct){
    this._events = this._events || {};
    this._events[event] = this._events[event] || [];
    this._events[event].push(fct);
  },
  off: function(event, fct){
    var n = arguments.length;
    if (n === 0) return delete this._events;
    if (n === 1) return delete this._events[event];

    this._events = this._events || {};
    if (event in this._events === false) return;
    this._events[event].splice(this._events[event].indexOf(fct), 1);
  },
  trigger: function(event /* , args... */){
    this._events = this._events || {};
    if (event in this._events === false) return;
    for (var i = 0; i < this._events[event].length; i++){
      this._events[event][i].apply(this, Array.prototype.slice.call(arguments, 1));
    }
  }
};

/**
 * Mixin will delegate all MicroEvent.js function in the destination object.
 *
 * - MicroEvent.mixin(Foobar) will make Foobar able to use MicroEvent
 *
 * @param {object} the object which will support MicroEvent
 */
MicroEvent.mixin = function(destObject){
  var props = ['on', 'off', 'trigger'];
  for (var i = 0; i < props.length; i++){
    destObject.prototype[props[i]] = MicroEvent.prototype[props[i]];
  }
};

var IS_MAC        = /Mac/.test(navigator.userAgent);

var KEY_A         = 65;
var KEY_COMMA     = 188;
var KEY_RETURN    = 13;
var KEY_ESC       = 27;
var KEY_LEFT      = 37;
var KEY_UP        = 38;
var KEY_RIGHT     = 39;
var KEY_DOWN      = 40;
var KEY_BACKSPACE = 8;
var KEY_DELETE    = 46;
var KEY_SHIFT     = 16;
var KEY_CMD       = IS_MAC ? 91 : 17;
var KEY_CTRL      = IS_MAC ? 18 : 17;
var KEY_TAB       = 9;

var TAG_SELECT    = 1;
var TAG_INPUT     = 2;

var isset = function(object) {
  return typeof object !== 'undefined';
};

/**
 * Converts a scalar to its best string representation
 * for hash keys and HTML attribute values.
 *
 * Transformations:
 *   'str'     -> 'str'
 *   null      -> ''
 *   undefined -> ''
 *   true      -> '1'
 *   false     -> '0'
 *   0         -> '0'
 *   1         -> '1'
 *
 * @param {string} value
 * @returns {string}
 */
var hash_key = function(value) {
  if (typeof value === 'undefined' || value === null) return '';
  if (typeof value === 'boolean') return value ? '1' : '0';
  return value + '';
};

/**
 * Escapes a string for use within HTML.
 *
 * @param {string} str
 * @returns {string}
 */
var escape_html = function(str) {
  return (str + '')
    .replace(/&/g, '&amp;')
    .replace(/</g, '&lt;')
    .replace(/>/g, '&gt;')
    .replace(/"/g, '&quot;');
};

/**
 * Escapes "$" characters in replacement strings.
 *
 * @param {string} str
 * @returns {string}
 */
var escape_replace = function(str) {
  return (str + '').replace(/\$/g, '$$$$');
};

var hook = {};

/**
 * Wraps `method` on `self` so that `fn`
 * is invoked before the original method.
 *
 * @param {object} self
 * @param {string} method
 * @param {function} fn
 */
hook.before = function(self, method, fn) {
  var original = self[method];
  self[method] = function() {
    fn.apply(self, arguments);
    return original.apply(self, arguments);
  };
};

/**
 * Wraps `method` on `self` so that `fn`
 * is invoked after the original method.
 *
 * @param {object} self
 * @param {string} method
 * @param {function} fn
 */
hook.after = function(self, method, fn) {
  var original = self[method];
  self[method] = function() {
    var result = original.apply(self, arguments);
    fn.apply(self, arguments);
    return result;
  };
};

/**
 * Builds a hash table out of an array of
 * objects, using the specified `key` within
 * each object.
 *
 * @param {string} key
 * @param {mixed} objects
 */
var build_hash_table = function(key, objects) {
  if (!$.isArray(objects)) return objects;
  var i, n, table = {};
  for (i = 0, n = objects.length; i < n; i++) {
    if (objects[i].hasOwnProperty(key)) {
      table[objects[i][key]] = objects[i];
    }
  }
  return table;
};

/**
 * Wraps `fn` so that it can only be invoked once.
 *
 * @param {function} fn
 * @returns {function}
 */
var once = function(fn) {
  var called = false;
  return function() {
    if (called) return;
    called = true;
    fn.apply(this, arguments);
  };
};

/**
 * Wraps `fn` so that it can only be called once
 * every `delay` milliseconds (invoked on the falling edge).
 *
 * @param {function} fn
 * @param {int} delay
 * @returns {function}
 */
var debounce = function(fn, delay) {
  var timeout;
  return function() {
    var self = this;
    var args = arguments;
    window.clearTimeout(timeout);
    timeout = window.setTimeout(function() {
      fn.apply(self, args);
    }, delay);
  };
};

/**
 * Debounce all fired events types listed in `types`
 * while executing the provided `fn`.
 *
 * @param {object} self
 * @param {array} types
 * @param {function} fn
 */
var debounce_events = function(self, types, fn) {
  var type;
  var trigger = self.trigger;
  var event_args = {};

  // override trigger method
  self.trigger = function() {
    var type = arguments[0];
    if (types.indexOf(type) !== -1) {
      event_args[type] = arguments;
    } else {
      return trigger.apply(self, arguments);
    }
  };

  // invoke provided function
  fn.apply(self, []);
  self.trigger = trigger;

  // trigger queued events
  for (type in event_args) {
    if (event_args.hasOwnProperty(type)) {
      trigger.apply(self, event_args[type]);
    }
  }
};

/**
 * A workaround for http://bugs.jquery.com/ticket/6696
 *
 * @param {object} $parent - Parent element to listen on.
 * @param {string} event - Event name.
 * @param {string} selector - Descendant selector to filter by.
 * @param {function} fn - Event handler.
 */
var watchChildEvent = function($parent, event, selector, fn) {
  $parent.on(event, selector, function(e) {
    var child = e.target;
    while (child && child.parentNode !== $parent[0]) {
      child = child.parentNode;
    }
    e.currentTarget = child;
    return fn.apply(this, [e]);
  });
};

/**
 * Determines the current selection within a text input control.
 * Returns an object containing:
 *   - start
 *   - length
 *
 * @param {object} input
 * @returns {object}
 */
var getSelection = function(input) {
  var result = {};
  if ('selectionStart' in input) {
    result.start = input.selectionStart;
    result.length = input.selectionEnd - result.start;
  } else if (document.selection) {
    input.focus();
    var sel = document.selection.createRange();
    var selLen = document.selection.createRange().text.length;
    sel.moveStart('character', -input.value.length);
    result.start = sel.text.length - selLen;
    result.length = selLen;
  }
  return result;
};

/**
 * Copies CSS properties from one element to another.
 *
 * @param {object} $from
 * @param {object} $to
 * @param {array} properties
 */
var transferStyles = function($from, $to, properties) {
  var i, n, styles = {};
  if (properties) {
    for (i = 0, n = properties.length; i < n; i++) {
      styles[properties[i]] = $from.css(properties[i]);
    }
  } else {
    styles = $from.css();
  }
  $to.css(styles);
};

/**
 * Measures the width of a string within a
 * parent element (in pixels).
 *
 * @param {string} str
 * @param {object} $parent
 * @returns {int}
 */
var measureString = function(str, $parent) {
  var $test = $('<test>').css({
    position: 'absolute',
    top: -99999,
    left: -99999,
    width: 'auto',
    padding: 0,
    whiteSpace: 'pre'
  }).text(str).appendTo('body');

  transferStyles($parent, $test, [
    'letterSpacing',
    'fontSize',
    'fontFamily',
    'fontWeight',
    'textTransform'
  ]);

  var width = $test.width();
  $test.remove();

  return width;
};

/**
 * Sets up an input to grow horizontally as the user
 * types. If the value is changed manually, you can
 * trigger the "update" handler to resize:
 *
 * $input.trigger('update');
 *
 * @param {object} $input
 */
var autoGrow = function($input) {
  var update = function(e) {
    var value, keyCode, printable, placeholder, width;
    var shift, character, selection;
    e = e || window.event || {};

    if (e.metaKey || e.altKey) return;
    if ($input.data('grow') === false) return;

    value = $input.val();
    if (e.type && e.type.toLowerCase() === 'keydown') {
      keyCode = e.keyCode;
      printable = (
        (keyCode >= 97 && keyCode <= 122) || // a-z
        (keyCode >= 65 && keyCode <= 90)  || // A-Z
        (keyCode >= 48 && keyCode <= 57)  || // 0-9
        keyCode === 32 // space
      );

      if (keyCode === KEY_DELETE || keyCode === KEY_BACKSPACE) {
        selection = getSelection($input[0]);
        if (selection.length) {
          value = value.substring(0, selection.start) + value.substring(selection.start + selection.length);
        } else if (keyCode === KEY_BACKSPACE && selection.start) {
          value = value.substring(0, selection.start - 1) + value.substring(selection.start + 1);
        } else if (keyCode === KEY_DELETE && typeof selection.start !== 'undefined') {
          value = value.substring(0, selection.start) + value.substring(selection.start + 1);
        }
      } else if (printable) {
        shift = e.shiftKey;
        character = String.fromCharCode(e.keyCode);
        if (shift) character = character.toUpperCase();
        else character = character.toLowerCase();
        value += character;
      }
    }

    placeholder = $input.attr('placeholder') || '';
    if (!value.length && placeholder.length) {
      value = placeholder;
    }

    width = measureString(value, $input) + 4;
    if (width !== $input.width()) {
      $input.width(width);
      $input.triggerHandler('resize');
    }
  };

  $input.on('keydown keyup update blur', update);
  update();
};

var Selectize = function($input, settings) {
  var key, i, n, dir, input, self = this;
  input = $input[0];
  input.selectize = self;

  // detect rtl environment
  dir = window.getComputedStyle ? window.getComputedStyle(input, null).getPropertyValue('direction') : input.currentStyle && input.currentStyle.direction;
  dir = dir || $input.parents('[dir]:first').attr('dir') || '';

  // setup default state
  $.extend(self, {
    settings         : settings,
    $input           : $input,
    tagType          : input.tagName.toLowerCase() === 'select' ? TAG_SELECT : TAG_INPUT,
    rtl              : /rtl/i.test(dir),

    eventNS          : '.selectize' + (++Selectize.count),
    highlightedValue : null,
    isOpen           : false,
    isDisabled       : false,
    isRequired       : $input.is('[required]'),
    isInvalid        : false,
    isLocked         : false,
    isFocused        : false,
    isInputHidden    : false,
    isSetup          : false,
    isShiftDown      : false,
    isCmdDown        : false,
    isCtrlDown       : false,
    ignoreFocus      : false,
    ignoreHover      : false,
    hasOptions       : false,
    currentResults   : null,
    lastValue        : '',
    caretPos         : 0,
    loading          : 0,
    loadedSearches   : {},

    $activeOption    : null,
    $activeItems     : [],

    optgroups        : {},
    options          : {},
    userOptions      : {},
    items            : [],
    renderCache      : {},
    onSearchChange   : debounce(self.onSearchChange, settings.loadThrottle)
  });

  // search system
  self.sifter = new Sifter(this.options, {diacritics: settings.diacritics});

  // build options table
  $.extend(self.options, build_hash_table(settings.valueField, settings.options));
  delete self.settings.options;

  // build optgroup table
  $.extend(self.optgroups, build_hash_table(settings.optgroupValueField, settings.optgroups));
  delete self.settings.optgroups;

  // option-dependent defaults
  self.settings.mode = self.settings.mode || (self.settings.maxItems === 1 ? 'single' : 'multi');
  if (typeof self.settings.hideSelected !== 'boolean') {
    self.settings.hideSelected = self.settings.mode === 'multi';
  }

  self.initializePlugins(self.settings.plugins);
  self.setupCallbacks();
  self.setupTemplates();
  self.setup();
};

// mixins
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

MicroEvent.mixin(Selectize);
MicroPlugin.mixin(Selectize);

// methods
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

$.extend(Selectize.prototype, {

  /**
   * Creates all elements and sets up event bindings.
   */
  setup: function() {
    var self      = this;
    var settings  = self.settings;
    var eventNS   = self.eventNS;
    var $window   = $(window);
    var $document = $(document);

    var $wrapper;
    var $control;
    var $control_input;
    var $dropdown;
    var $dropdown_content;
    var $dropdown_parent;
    var inputMode;
    var timeout_blur;
    var timeout_focus;
    var tab_index;
    var classes;
    var classes_plugins;

    inputMode         = self.settings.mode;
    tab_index         = self.$input.attr('tabindex') || '';
    classes           = self.$input.attr('class') || '';

    $wrapper          = $('<div>').addClass(settings.wrapperClass).addClass(classes).addClass(inputMode);
    $control          = $('<div>').addClass(settings.inputClass).addClass('items').appendTo($wrapper);
    $control_input    = $('<input type="text" autocomplete="off">').appendTo($control).attr('tabindex', tab_index);
    $dropdown_parent  = $(settings.dropdownParent || $wrapper);
    $dropdown         = $('<div>').addClass(settings.dropdownClass).addClass(classes).addClass(inputMode).hide().appendTo($dropdown_parent);
    $dropdown_content = $('<div>').addClass(settings.dropdownContentClass).appendTo($dropdown);

    $wrapper.css({
      width: self.$input[0].style.width
    });

    if (self.plugins.names.length) {
      classes_plugins = 'plugin-' + self.plugins.names.join(' plugin-');
      $wrapper.addClass(classes_plugins);
      $dropdown.addClass(classes_plugins);
    }

    if ((settings.maxItems === null || settings.maxItems > 1) && self.tagType === TAG_SELECT) {
      self.$input.attr('multiple', 'multiple');
    }

    if (self.settings.placeholder) {
      $control_input.attr('placeholder', settings.placeholder);
    }

    self.$wrapper          = $wrapper;
    self.$control          = $control;
    self.$control_input    = $control_input;
    self.$dropdown         = $dropdown;
    self.$dropdown_content = $dropdown_content;

    $dropdown.on('mouseenter', '[data-selectable]', function() { return self.onOptionHover.apply(self, arguments); });
    $dropdown.on('mousedown', '[data-selectable]', function() { return self.onOptionSelect.apply(self, arguments); });
    watchChildEvent($control, 'mousedown', '*:not(input)', function() { return self.onItemSelect.apply(self, arguments); });
    watchChildEvent($control, 'mousedown', '.item-clickable', function() { self.trigger('item_selected', $(this).parent()); });
    autoGrow($control_input);

    $control.on({
      mousedown : function() { return self.onMouseDown.apply(self, arguments); },
      click     : function() { return self.onClick.apply(self, arguments); }
    });

    $control_input.on({
      mousedown : function(e) { e.stopPropagation(); },
      keydown   : function() { return self.onKeyDown.apply(self, arguments); },
      keyup     : function() { return self.onKeyUp.apply(self, arguments); },
      keypress  : function() { return self.onKeyPress.apply(self, arguments); },
      resize    : function() { self.positionDropdown.apply(self, []); },
      blur      : function() { return self.onBlur.apply(self, arguments); },
      focus     : function() { return self.onFocus.apply(self, arguments); }
    });

    $document.on('keydown' + eventNS, function(e) {
      self.isCmdDown = e[IS_MAC ? 'metaKey' : 'ctrlKey'];
      self.isCtrlDown = e[IS_MAC ? 'altKey' : 'ctrlKey'];
      self.isShiftDown = e.shiftKey;
    });

    $document.on('keyup' + eventNS, function(e) {
      if (e.keyCode === KEY_CTRL) self.isCtrlDown = false;
      if (e.keyCode === KEY_SHIFT) self.isShiftDown = false;
      if (e.keyCode === KEY_CMD) self.isCmdDown = false;
    });

    $document.on('mousedown' + eventNS, function(e) {
      if (self.isFocused) {
        // prevent events on the dropdown scrollbar from causing the control to blur
        if (e.target === self.$dropdown[0] || e.target.parentNode === self.$dropdown[0]) {
          return false;
        }
        // blur on click outside
        if (!self.$control.has(e.target).length && e.target !== self.$control[0]) {
          self.blur();
        }
      }
    });

    $window.on(['scroll' + eventNS, 'resize' + eventNS].join(' '), function() {
      if (self.isOpen) {
        self.positionDropdown.apply(self, arguments);
      }
    });
    $window.on('mousemove' + eventNS, function() {
      self.ignoreHover = false;
    });

    // store original children and tab index so that they can be
    // restored when the destroy() method is called.
    this.revertSettings = {
      $children : self.$input.children().detach(),
      tabindex  : self.$input.attr('tabindex')
    };

    self.$input.attr('tabindex', -1).hide().after(self.$wrapper);

    if ($.isArray(settings.items)) {
      self.setValue(settings.items);
      delete settings.items;
    }

    // feature detect for the validation API
    if (self.$input[0].validity) {
      self.$input.on('invalid' + eventNS, function(e) {
        e.preventDefault();
        self.isInvalid = true;
        self.refreshState();
      });
    }

    self.updateOriginalInput();
    self.refreshItems();
    self.refreshState();
    self.updatePlaceholder();
    self.isSetup = true;

    if (self.$input.is(':disabled')) {
      self.disable();
    }

    self.on('change', this.onChange);
    self.trigger('initialize');

    // preload options
    if (settings.preload) {
      self.onSearchChange('');
    }
  },

  /**
   * Sets up default rendering functions.
   */
  setupTemplates: function() {
    var self = this;
    var field_label = self.settings.labelField;
    var field_optgroup = self.settings.optgroupLabelField;

    var templates = {
      'optgroup': function(data) {
        return '<div class="optgroup">' + data.html + '</div>';
      },
      'optgroup_header': function(data, escape) {
        return '<div class="optgroup-header">' + escape(data[field_optgroup]) + '</div>';
      },
      'option': function(data, escape) {
        return '<div class="option">' + escape(data[field_label]) + '</div>';
      },
      'item': function(data, escape) {
        return '<div class="item">' + escape(data[field_label]) + '</div>';
      },
      'option_create': function(data, escape) {
        return '<div class="create">Add <strong>' + escape(data.input) + '</strong>&hellip;</div>';
      }
    };

    self.settings.render = $.extend({}, templates, self.settings.render);
  },

  /**
   * Maps fired events to callbacks provided
   * in the settings used when creating the control.
   */
  setupCallbacks: function() {
    var key, fn, callbacks = {
      'initialize'     : 'onInitialize',
      'change'         : 'onChange',
      'item_add'       : 'onItemAdd',
      'item_remove'    : 'onItemRemove',
      'item_selected'  : 'onItemSelected',
      'clear'          : 'onClear',
      'option_add'     : 'onOptionAdd',
      'optionActive'  : 'onOptionActive',
      'option_remove'  : 'onOptionRemove',
      'option_clear'   : 'onOptionClear',
      'dropdown_open'  : 'onDropdownOpen',
      'dropdown_close' : 'onDropdownClose',
      'type'           : 'onType'
    };

    for (key in callbacks) {
      if (callbacks.hasOwnProperty(key)) {
        fn = this.settings[callbacks[key]];
        if (fn) this.on(key, fn);
      }
    }
  },

  /**
   * Triggered when the main control element
   * has a click event.
   *
   * @param {object} e
   * @return {boolean}
   */
  onClick: function(e) {
    var self = this;

    // necessary for mobile webkit devices (manual focus triggering
    // is ignored unless invoked within a click event)
    if (!self.isFocused) {
      self.focus();
      e.preventDefault();
    }
  },

  /**
   * Triggered when the main control element
   * has a mouse down event.
   *
   * @param {object} e
   * @return {boolean}
   */
  onMouseDown: function(e) {
    var self = this;
    var defaultPrevented = e.isDefaultPrevented();
    var $target = $(e.target);

    if (self.isFocused) {
      // retain focus by preventing native handling. if the
      // event target is the input it should not be modified.
      // otherwise, text selection within the input won't work.
      if (e.target !== self.$control_input[0]) {
        if (self.settings.mode === 'single') {
          // toggle dropdown
          self.isOpen ? self.close() : self.open();
        } else if (!defaultPrevented) {
          self.setActiveItem(null);
        }
        return false;
      }
    } else {
      // give control focus
      if (!defaultPrevented) {
        window.setTimeout(function() {
          self.focus();
        }, 0);
      }
    }
  },

  /**
   * Triggered when the value of the control has been changed.
   * This should propagate the event to the original DOM
   * input / select element.
   */
  onChange: function() {
    this.$input.trigger('change');
  },

  /**
   * Triggered on <input> keypress.
   *
   * @param {object} e
   * @returns {boolean}
   */
  onKeyPress: function(e) {
    if (this.isLocked) return e && e.preventDefault();
    var character = String.fromCharCode(e.keyCode || e.which);
    if (this.settings.create && character === this.settings.delimiter) {
      this.createItem();
      e.preventDefault();
      return false;
    }
  },

  /**
   * Triggered on <input> keydown.
   *
   * @param {object} e
   * @returns {boolean}
   */
  onKeyDown: function(e) {
    var isInput = e.target === this.$control_input[0];
    var self = this;

    if (self.isLocked) {
      if (e.keyCode !== KEY_TAB) {
        e.preventDefault();
      }
      return;
    }

    switch (e.keyCode) {
      case KEY_A:
        if (self.isCmdDown) {
          self.selectAll();
          return;
        }
        break;
      case KEY_ESC:
        self.close();
        return;
      case KEY_DOWN:
        if (!self.isOpen && self.hasOptions) {
          self.open();
        } else if (self.$activeOption) {
          self.ignoreHover = true;
          var $next = self.getAdjacentOption(self.$activeOption, 1);
          if ($next.length) self.setActiveOption($next, true, true);
        }
        e.preventDefault();
        return;
      case KEY_UP:
        if (self.$activeOption) {
          self.ignoreHover = true;
          var $prev = self.getAdjacentOption(self.$activeOption, -1);
          if ($prev.length) self.setActiveOption($prev, true, true);
        }
        e.preventDefault();
        return;
      case KEY_RETURN:
        if (self.isOpen && self.$activeOption) {
          self.onOptionSelect({currentTarget: self.$activeOption});
        }
        e.preventDefault();
        return;
      case KEY_LEFT:
        self.advanceSelection(-1, e);
        return;
      case KEY_RIGHT:
        self.advanceSelection(1, e);
        return;
      case KEY_TAB:
        if (self.settings.create && self.createItem()) {
          e.preventDefault();
        }
        return;
      case KEY_BACKSPACE:
      case KEY_DELETE:
        self.deleteSelection(e);
        return;
    }
    if (self.isFull() || self.isInputHidden) {
      e.preventDefault();
      return;
    }
  },

  /**
   * Triggered on <input> keyup.
   *
   * @param {object} e
   * @returns {boolean}
   */
  onKeyUp: function(e) {
    var self = this;

    if (self.isLocked) return e && e.preventDefault();
    var value = self.$control_input.val() || '';
    if (self.lastValue !== value) {
      self.lastValue = value;
      self.onSearchChange(value);
      self.refreshOptions();
      self.trigger('type', value);
    }
  },

  /**
   * Invokes the user-provide option provider / loader.
   *
   * Note: this function is debounced in the Selectize
   * constructor (by `settings.loadDelay` milliseconds)
   *
   * @param {string} value
   */
  onSearchChange: function(value) {
    var self = this;
    var fn = self.settings.load;
    if (!fn) return;
    if (self.loadedSearches.hasOwnProperty(value)) return;
    self.loadedSearches[value] = true;
    self.load(function(callback) {
      fn.apply(self, [value, callback]);
    });
  },

  /**
   * Triggered on <input> focus.
   *
   * @param {object} e (optional)
   * @returns {boolean}
   */
  onFocus: function(e) {
    var self = this;

    self.isFocused = true;
    if (self.isDisabled) {
      self.blur();
      e && e.preventDefault();
      return false;
    }

    if (self.ignoreFocus) return;
    if (self.settings.preload === 'focus') self.onSearchChange('');

    if (!self.$activeItems.length) {
      self.showInput();
      self.setActiveItem(null);
      self.refreshOptions(!!self.settings.openOnFocus);
    }

    self.refreshState();
  },

  /**
   * Triggered on <input> blur.
   *
   * @param {object} e
   * @returns {boolean}
   */
  onBlur: function(e) {
    var self = this;
    self.isFocused = false;
    if (self.ignoreFocus) return;

    if (self.settings.create && self.settings.createOnBlur) {
      self.createItem();
    }

    self.close();
    self.setTextboxValue('');
    //self.setActiveItem(null);
    self.setActiveOption(null);
    self.setCaret(self.items.length);
    self.refreshState();
  },

  /**
   * Triggered when the user rolls over
   * an option in the autocomplete dropdown menu.
   *
   * @param {object} e
   * @returns {boolean}
   */
  onOptionHover: function(e) {
    if (this.ignoreHover) return;
    this.setActiveOption(e.currentTarget, false);
  },

  /**
   * Triggered when the user clicks on an option
   * in the autocomplete dropdown menu.
   *
   * @param {object} e
   * @returns {boolean}
   */
  onOptionSelect: function(e) {
    var value, $target, $option, self = this;

    if (e.preventDefault) {
      e.preventDefault();
      e.stopPropagation();
    }

    $target = $(e.currentTarget);
    if ($target.hasClass('create')) {
      self.createItem();
    } else {
      value = $target.attr('data-value');
      if (value) {
        self.lastQuery = null;
        self.setTextboxValue('');
        self.addItem(value);
        if (!self.settings.hideSelected && e.type && /mouse/.test(e.type)) {
          self.setActiveOption(self.getOption(value));
        }
      }
    }
  },

  /**
   * Triggered when the user clicks on an item
   * that has been selected.
   *
   * @param {object} e
   * @returns {boolean}
   */
  onItemSelect: function(e) {
    var self = this;

    if (self.isLocked) return;
    if (self.settings.mode === 'multi') {
      var $el = $(e.currentTarget);
      e.preventDefault();

      if ($el.hasClass('active')) {
        $el.removeClass('active');
        self.trigger('optionActive', null);
      } else {
        self.setActiveItem(e.currentTarget, e);
        self.trigger('optionActive', $el);
      }
    }
  },

  /**
   * Invokes the provided method that provides
   * results to a callback---which are then added
   * as options to the control.
   *
   * @param {function} fn
   */
  load: function(fn) {
    var self = this;
    var $wrapper = self.$wrapper.addClass('loading');

    self.loading++;
    fn.apply(self, [function(results) {
      self.loading = Math.max(self.loading - 1, 0);
      if (results && results.length) {
        self.addOption(results);
        self.refreshOptions(self.isFocused && !self.isInputHidden);
      }
      if (!self.loading) {
        $wrapper.removeClass('loading');
      }
      self.trigger('load', results);
    }]);
  },

  /**
   * Sets the input field of the control to the specified value.
   *
   * @param {string} value
   */
  setTextboxValue: function(value) {
    this.$control_input.val(value).triggerHandler('update');
    this.lastValue = value;
  },

  /**
   * Returns the value of the control. If multiple items
   * can be selected (e.g. <select multiple>), this returns
   * an array. If only one item can be selected, this
   * returns a string.
   *
   * @returns {mixed}
   */
  getValue: function() {
    if (this.tagType === TAG_SELECT && this.$input.attr('multiple')) {
      return this.items;
    } else {
      return this.items.join(this.settings.delimiter);
    }
  },

  /**
   * Resets the selected items to the given value.
   *
   * @param {mixed} value
   */
  setValue: function(value) {
    debounce_events(this, ['change'], function() {
      this.clear();
      var items = $.isArray(value) ? value : [value];
      for (var i = 0, n = items.length; i < n; i++) {
        this.addItem(items[i]);
      }
    });
  },

  /**
   * Sets the selected item.
   *
   * @param {object} $item
   * @param {object} e (optional)
   */
  setActiveItem: function($item, e, silent) {
    var self = this;
    var eventName;
    var i, idx, begin, end, item, swap;
    var $last;

    if (self.settings.mode === 'single') return;
    $item = $($item);

    // clear the active selection
    if (!$item.length) {
      $(self.$activeItems).removeClass('active');
      self.trigger('optionActive', null);
      self.$activeItems = [];
      if (self.isFocused) {
        self.showInput();
      }
      return;
    }

    // modify selection
    eventName = e && e.type.toLowerCase();

    if (eventName === 'mousedown' && self.isShiftDown && self.$activeItems.length) {
      $last = self.$control.children('.active:last');
      begin = Array.prototype.indexOf.apply(self.$control[0].childNodes, [$last[0]]);
      end   = Array.prototype.indexOf.apply(self.$control[0].childNodes, [$item[0]]);
      if (begin > end) {
        swap  = begin;
        begin = end;
        end   = swap;
      }
      for (i = begin; i <= end; i++) {
        item = self.$control[0].childNodes[i];
        if (self.$activeItems.indexOf(item) === -1) {
          $(item).addClass('active');
          self.$activeItems.push(item);
        }
      }
      e.preventDefault();
    } else if ((eventName === 'mousedown' && self.isCtrlDown) || (eventName === 'keydown' && this.isShiftDown)) {
      if ($item.hasClass('active')) {
        idx = self.$activeItems.indexOf($item[0]);
        self.$activeItems.splice(idx, 1);
        $item.removeClass('active');
      } else {
        self.$activeItems.push($item.addClass('active')[0]);
      }
    } else {
      $(self.$activeItems).removeClass('active');
      self.$activeItems = [$item.addClass('active')[0]];
    }
    if (!silent) {
      self.trigger('optionActive', $(self.$activeItems[0]));
    }

    // ensure control has focus
    self.hideInput();
    if (!this.isFocused) {
      self.focus();
    }
  },

  /**
   * Sets the selected item in the dropdown menu
   * of available options.
   *
   * @param {object} $object
   * @param {boolean} scroll
   * @param {boolean} animate
   */
  setActiveOption: function($option, scroll, animate) {
    var height_menu, height_item, y;
    var scroll_top, scroll_bottom;
    var self = this;

    if (self.$activeOption) self.$activeOption.removeClass('active');
    self.$activeOption = null;

    $option = $($option);
    if (!$option.length) return;

    self.$activeOption = $option.addClass('active');

    if (scroll || !isset(scroll)) {

      height_menu   = self.$dropdown_content.height();
      height_item   = self.$activeOption.outerHeight(true);
      scroll        = self.$dropdown_content.scrollTop() || 0;
      y             = self.$activeOption.offset().top - self.$dropdown_content.offset().top + scroll;
      scroll_top    = y;
      scroll_bottom = y - height_menu + height_item;

      if (y + height_item > height_menu + scroll) {
        self.$dropdown_content.stop().animate({scrollTop: scroll_bottom}, animate ? self.settings.scrollDuration : 0);
      } else if (y < scroll) {
        self.$dropdown_content.stop().animate({scrollTop: scroll_top}, animate ? self.settings.scrollDuration : 0);
      }

    }
  },

  /**
   * Selects all items (CTRL + A).
   */
  selectAll: function() {
    var self = this;
    if (self.settings.mode === 'single') return;

    self.$activeItems = Array.prototype.slice.apply(self.$control.children(':not(input)').addClass('active'));
    if (self.$activeItems.length) {
      self.hideInput();
      self.close();
    }
    self.focus();
  },

  /**
   * Hides the input element out of view, while
   * retaining its focus.
   */
  hideInput: function() {
    var self = this;

    self.setTextboxValue('');
    self.$control_input.css({opacity: 0, position: 'absolute', left: self.rtl ? 10000 : -10000});
    self.isInputHidden = true;
  },

  /**
   * Restores input visibility.
   */
  showInput: function() {
    this.$control_input.css({opacity: 1, position: 'relative', left: 0});
    this.isInputHidden = false;
  },

  /**
   * Gives the control focus. If "trigger" is falsy,
   * focus handlers won't be fired--causing the focus
   * to happen silently in the background.
   *
   * @param {boolean} trigger
   */
  focus: function() {
    var self = this;
    if (self.isDisabled) return;

    self.ignoreFocus = true;
    self.$control_input[0].focus();
    window.setTimeout(function() {
      self.ignoreFocus = false;
      self.onFocus();
    }, 0);
  },

  /**
   * Forces the control out of focus.
   */
  blur: function() {
    this.$control_input.trigger('blur');
  },

  /**
   * Returns a function that scores an object
   * to show how good of a match it is to the
   * provided query.
   *
   * @param {string} query
   * @param {object} options
   * @return {function}
   */
  getScoreFunction: function(query) {
    return this.sifter.getScoreFunction(query, this.getSearchOptions());
  },

  /**
   * Returns search options for sifter (the system
   * for scoring and sorting results).
   *
   * @see https://github.com/brianreavis/sifter.js
   * @return {object}
   */
  getSearchOptions: function() {
    var settings = this.settings;
    var sort = settings.sortField;
    if (typeof sort === 'string') {
      sort = {field: sort};
    }

    return {
      fields      : settings.searchField,
      conjunction : settings.searchConjunction,
      sort        : sort
    };
  },

  /**
   * Searches through available options and returns
   * a sorted array of matches.
   *
   * Returns an object containing:
   *
   *   - query {string}
   *   - tokens {array}
   *   - total {int}
   *   - items {array}
   *
   * @param {string} query
   * @returns {object}
   */
  search: function(query) {
    var i, value, score, result, calculateScore;
    var self     = this;
    var settings = self.settings;
    var options  = this.getSearchOptions();

    // validate user-provided result scoring function
    if (settings.score) {
      calculateScore = self.settings.score.apply(this, [query]);
      if (typeof calculateScore !== 'function') {
        throw new Error('Selectize "score" setting must be a function that returns a function');
      }
    }

    // perform search
    if (query !== self.lastQuery) {
      self.lastQuery = query;
      result = self.sifter.search(query, $.extend(options, {score: calculateScore}));
      self.currentResults = result;
    } else {
      result = $.extend(true, {}, self.currentResults);
    }

    // filter out selected items
    if (settings.hideSelected) {
      for (i = result.items.length - 1; i >= 0; i--) {
        if (self.items.indexOf(hash_key(result.items[i].id)) !== -1) {
          result.items.splice(i, 1);
        }
      }
    }

    return result;
  },

  /**
   * Refreshes the list of available options shown
   * in the autocomplete dropdown menu.
   *
   * @param {boolean} triggerDropdown
   */
  refreshOptions: function(triggerDropdown) {
    var i, j, k, n, groups, groups_order, option, option_html, optgroup, optgroups, html, html_children, has_create_option;
    var $active, $active_before, $create;

    if (typeof triggerDropdown === 'undefined') {
      triggerDropdown = true;
    }

    var self              = this;
    var query             = self.$control_input.val();
    var results           = self.search(query);
    var $dropdown_content = self.$dropdown_content;
    var active_before     = self.$activeOption && hash_key(self.$activeOption.attr('data-value'));

    // build markup
    n = results.items.length;
    if (typeof self.settings.maxOptions === 'number') {
      n = Math.min(n, self.settings.maxOptions);
    }

    // render and group available options individually
    groups = {};

    if (self.settings.optgroupOrder) {
      groups_order = self.settings.optgroupOrder;
      for (i = 0; i < groups_order.length; i++) {
        groups[groups_order[i]] = [];
      }
    } else {
      groups_order = [];
    }

    for (i = 0; i < n; i++) {
      option      = self.options[results.items[i].id];
      option_html = self.render('option', option);
      optgroup    = option[self.settings.optgroupField] || '';
      optgroups   = $.isArray(optgroup) ? optgroup : [optgroup];

      for (j = 0, k = optgroups && optgroups.length; j < k; j++) {
        optgroup = optgroups[j];
        if (!self.optgroups.hasOwnProperty(optgroup)) {
          optgroup = '';
        }
        if (!groups.hasOwnProperty(optgroup)) {
          groups[optgroup] = [];
          groups_order.push(optgroup);
        }
        groups[optgroup].push(option_html);
      }
    }

    // render optgroup headers & join groups
    html = [];
    for (i = 0, n = groups_order.length; i < n; i++) {
      optgroup = groups_order[i];
      if (self.optgroups.hasOwnProperty(optgroup) && groups[optgroup].length) {
        // render the optgroup header and options within it,
        // then pass it to the wrapper template
        html_children = self.render('optgroup_header', self.optgroups[optgroup]) || '';
        html_children += groups[optgroup].join('');
        html.push(self.render('optgroup', $.extend({}, self.optgroups[optgroup], {
          html: html_children
        })));
      } else {
        html.push(groups[optgroup].join(''));
      }
    }

    $dropdown_content.html(html.join(''));

    // highlight matching terms inline
    if (self.settings.highlight && results.query.length && results.tokens.length) {
      for (i = 0, n = results.tokens.length; i < n; i++) {
        highlight($dropdown_content, results.tokens[i].regex);
      }
    }

    // add "selected" class to selected options
    if (!self.settings.hideSelected) {
      for (i = 0, n = self.items.length; i < n; i++) {
        self.getOption(self.items[i]).addClass('selected');
      }
    }

    // add create option
    has_create_option = self.settings.create && results.query.length;
    if (has_create_option) {
      $dropdown_content.prepend(self.render('option_create', {input: query}));
      $create = $($dropdown_content[0].childNodes[0]);
    }

    // activate
    self.hasOptions = results.items.length > 0 || has_create_option;
    if (self.hasOptions) {
      if (results.items.length > 0) {
        $active_before = active_before && self.getOption(active_before);
        if ($active_before && $active_before.length) {
          $active = $active_before;
        } else if (self.settings.mode === 'single' && self.items.length) {
          $active = self.getOption(self.items[0]);
        }
        if (!$active || !$active.length) {
          if ($create && !self.settings.addPrecedence) {
            $active = self.getAdjacentOption($create, 1);
          } else {
            $active = $dropdown_content.find('[data-selectable]:first');
          }
        }
      } else {
        $active = $create;
      }
      self.setActiveOption($active);
      if (triggerDropdown && !self.isOpen) { self.open(); }
    } else {
      self.setActiveOption(null);
      if (triggerDropdown && self.isOpen) { self.close(); }
    }
  },

  /**
   * Adds an available option. If it already exists,
   * nothing will happen. Note: this does not refresh
   * the options list dropdown (use `refreshOptions`
   * for that).
   *
   * Usage:
   *
   *   this.addOption(data)
   *
   * @param {object} data
   */
  addOption: function(data) {
    var i, n, optgroup, value, self = this;

    if ($.isArray(data)) {
      for (i = 0, n = data.length; i < n; i++) {
        self.addOption(data[i]);
      }
      return;
    }

    value = hash_key(data[self.settings.valueField]);
    if (!value || self.options.hasOwnProperty(value)) return;

    self.userOptions[value] = true;
    self.options[value] = data;
    self.lastQuery = null;
    self.trigger('option_add', value, data);
  },

  /**
   * Registers a new optgroup for options
   * to be bucketed into.
   *
   * @param {string} id
   * @param {object} data
   */
  addOptionGroup: function(id, data) {
    this.optgroups[id] = data;
    this.trigger('optgroup_add', id, data);
  },

  /**
   * Updates an option available for selection. If
   * it is visible in the selected items or options
   * dropdown, it will be re-rendered automatically.
   *
   * @param {string} value
   * @param {object} data
   */
  updateOption: function(value, data) {
    var self = this;
    var $item, $item_new;
    var value_new, index_item, cache_items, cache_options;

    value     = hash_key(value);
    value_new = hash_key(data[self.settings.valueField]);

    // sanity checks
    if (!self.options.hasOwnProperty(value)) return;
    if (!value_new) throw new Error('Value must be set in option data');

    // update references
    if (value_new !== value) {
      delete self.options[value];
      index_item = self.items.indexOf(value);
      if (index_item !== -1) {
        self.items.splice(index_item, 1, value_new);
      }
    }
    self.options[value_new] = data;

    // invalidate render cache
    cache_items = self.renderCache['item'];
    cache_options = self.renderCache['option'];

    if (isset(cache_items)) {
      delete cache_items[value];
      delete cache_items[value_new];
    }
    if (isset(cache_options)) {
      delete cache_options[value];
      delete cache_options[value_new];
    }

    // update the item if it's selected
    if (self.items.indexOf(value_new) !== -1) {
      $item = self.getItem(value);
      $item_new = $(self.render('item', data));
      if ($item.hasClass('active')) $item_new.addClass('active');
      $item.replaceWith($item_new);
    }

    // update dropdown contents
    if (self.isOpen) {
      self.refreshOptions(false);
    }
  },

  /**
   * Removes a single option.
   *
   * @param {string} value
   */
  removeOption: function(value) {
    var self = this;

    value = hash_key(value);
    delete self.userOptions[value];
    delete self.options[value];
    self.lastQuery = null;
    self.trigger('option_remove', value);
    self.removeItem(value);
  },

  /**
   * Clears all options.
   */
  clearOptions: function() {
    var self = this;

    self.loadedSearches = {};
    self.userOptions = {};
    self.options = self.sifter.items = {};
    self.lastQuery = null;
    self.trigger('option_clear');
    self.clear();
  },

  /**
   * Returns the jQuery element of the option
   * matching the given value.
   *
   * @param {string} value
   * @returns {object}
   */
  getOption: function(value) {
    return this.getElementWithValue(value, this.$dropdown_content.find('[data-selectable]'));
  },

  /**
   * Returns the jQuery element of the next or
   * previous selectable option.
   *
   * @param {object} $option
   * @param {int} direction  can be 1 for next or -1 for previous
   * @return {object}
   */
  getAdjacentOption: function($option, direction) {
    var $options = this.$dropdown.find('[data-selectable]');
    var index    = $options.index($option) + direction;

    return index >= 0 && index < $options.length ? $options.eq(index) : $();
  },

  /**
   * Finds the first element with a "data-value" attribute
   * that matches the given value.
   *
   * @param {mixed} value
   * @param {object} $els
   * @return {object}
   */
  getElementWithValue: function(value, $els) {
    value = hash_key(value);

    if (value) {
      for (var i = 0, n = $els.length; i < n; i++) {
        if ($els[i].getAttribute('data-value') === value) {
          return $($els[i]);
        }
      }
    }

    return $();
  },

  /**
   * Returns the jQuery element of the item
   * matching the given value.
   *
   * @param {string} value
   * @returns {object}
   */
  getItem: function(value) {
    return this.getElementWithValue(value, this.$control.children());
  },

  /**
   * "Selects" an item. Adds it to the list
   * at the current caret position.
   *
   * @param {string} value
   */
  addItem: function(value, silent) {
    debounce_events(this, ['change'], function() {
      var $item, $option;
      var self = this;
      var inputMode = self.settings.mode;
      var i, active, options, value_next;
      value = hash_key(value);

      if (self.items.indexOf(value) !== -1) {
        if (inputMode === 'single') self.close();
        return;
      }

      if (!self.options.hasOwnProperty(value)) return;
      if (inputMode === 'single') self.clear();
      if (inputMode === 'multi' && self.isFull()) return;

      $item = $(self.render('item', self.options[value]));
      self.items.splice(self.caretPos, 0, value);
      self.insertAtCaret($item);
      self.refreshState();

      if (self.isSetup) {
        options = self.$dropdown_content.find('[data-selectable]');

        // update menu / remove the option
        $option = self.getOption(value);
        value_next = self.getAdjacentOption($option, 1).attr('data-value');
        self.refreshOptions(self.isFocused && inputMode !== 'single');
        if (value_next) {
          self.setActiveOption(self.getOption(value_next));
        }

        // hide the menu if the maximum number of items have been selected or no options are left
        if (!options.length || (self.settings.maxItems !== null && self.items.length >= self.settings.maxItems)) {
          self.close();
        } else {
          self.positionDropdown();
        }

        self.updatePlaceholder();
        if (!silent) {
          self.trigger('item_add', value, $item);
        }
        self.updateOriginalInput();
      }
    });
  },

  /**
   * Removes the selected item matching
   * the provided value.
   *
   * @param {string} value
   */
  removeItem: function(value) {
    var self = this;
    var $item, i, idx;

    $item = (typeof value === 'object') ? value : self.getItem(value);
    value = hash_key($item.attr('data-value'));
    i = self.items.indexOf(value);

    if (i !== -1) {
      $item.remove();
      if ($item.hasClass('active')) {
        idx = self.$activeItems.indexOf($item[0]);
        self.$activeItems.splice(idx, 1);
      }

      self.items.splice(i, 1);
      self.lastQuery = null;
      if (!self.settings.persist && self.userOptions.hasOwnProperty(value)) {
        self.removeOption(value);
      }

      if (i < self.caretPos) {
        self.setCaret(self.caretPos - 1);
      }

      self.refreshState();
      self.updatePlaceholder();
      self.updateOriginalInput();
      self.positionDropdown();
      self.trigger('item_remove', value);
    }
  },

  /**
   * Invokes the `create` method provided in the
   * selectize options that should provide the data
   * for the new item, given the user input.
   *
   * Once this completes, it will be added
   * to the item list.
   *
   * @return {boolean}
   */
  createItem: function() {
    var self  = this;
    var input = $.trim(self.$control_input.val() || '');
    var caret = self.caretPos;
    if (!input.length) return false;
    self.lock();

    var setup = (typeof self.settings.create === 'function') ? this.settings.create : function(input) {
      var data = {};
      data[self.settings.labelField] = input;
      data[self.settings.valueField] = input;
      return data;
    };

    var create = once(function(data) {
      self.unlock();

      if (!data || typeof data !== 'object') return;
      var value = hash_key(data[self.settings.valueField]);
      if (!value) return;

      self.setTextboxValue('');
      self.addOption(data);
      self.setCaret(caret);
      self.addItem(value);
      self.refreshOptions(self.settings.mode !== 'single');
    });

    var output = setup.apply(this, [input, create]);
    if (typeof output !== 'undefined') {
      create(output);
    }

    return true;
  },

  /**
   * Re-renders the selected item lists.
   */
  refreshItems: function() {
    this.lastQuery = null;

    if (this.isSetup) {
      for (var i = 0; i < this.items.length; i++) {
        this.addItem(this.items);
      }
    }

    this.refreshState();
    this.updateOriginalInput();
  },

  /**
   * Updates all state-dependent attributes
   * and CSS classes.
   */
  refreshState: function() {
    var self = this;
    var invalid = self.isRequired && !self.items.length;
    if (!invalid) self.isInvalid = false;
    self.$control_input.prop('required', invalid);
    self.refreshClasses();
  },

  /**
   * Updates all state-dependent CSS classes.
   */
  refreshClasses: function() {
    var self     = this;
    var isFull   = self.isFull();
    var isLocked = self.isLocked;

    self.$wrapper
      .toggleClass('rtl', self.rtl);

    self.$control
      .toggleClass('focus', self.isFocused)
      .toggleClass('disabled', self.isDisabled)
      .toggleClass('required', self.isRequired)
      .toggleClass('invalid', self.isInvalid)
      .toggleClass('locked', isLocked)
      .toggleClass('full', isFull).toggleClass('not-full', !isFull)
      .toggleClass('input-active', self.isFocused && !self.isInputHidden)
      .toggleClass('dropdown-active', self.isOpen)
      .toggleClass('has-options', !$.isEmptyObject(self.options))
      .toggleClass('has-items', self.items.length > 0);

    self.$control_input.data('grow', !isFull && !isLocked);
  },

  /**
   * Determines whether or not more items can be added
   * to the control without exceeding the user-defined maximum.
   *
   * @returns {boolean}
   */
  isFull: function() {
    return this.settings.maxItems !== null && this.items.length >= this.settings.maxItems;
  },

  /**
   * Refreshes the original <select> or <input>
   * element to reflect the current state.
   */
  updateOriginalInput: function() {
    var i, n, options, self = this;

    if (self.$input[0].tagName.toLowerCase() === 'select') {
      options = [];
      for (i = 0, n = self.items.length; i < n; i++) {
        options.push('<option value="' + escape_html(self.items[i]) + '" selected="selected"></option>');
      }
      if (!options.length && !this.$input.attr('multiple')) {
        options.push('<option value="" selected="selected"></option>');
      }
      self.$input.html(options.join(''));
    } else {
      self.$input.val(self.getValue());
    }

    if (self.isSetup) {
      self.trigger('change', self.$input.val());
    }
  },

  /**
   * Shows/hide the input placeholder depending
   * on if there items in the list already.
   */
  updatePlaceholder: function() {
    if (!this.settings.placeholder) return;
    var $input = this.$control_input;

    if (this.items.length) {
      $input.removeAttr('placeholder');
    } else {
      $input.attr('placeholder', this.settings.placeholder);
    }
    $input.triggerHandler('update');
  },

  /**
   * Shows the autocomplete dropdown containing
   * the available options.
   */
  open: function() {
    var self = this;

    if (self.isLocked || self.isOpen || (self.settings.mode === 'multi' && self.isFull())) return;
    self.focus();
    self.isOpen = true;
    self.refreshState();
    self.$dropdown.css({visibility: 'hidden', display: 'block'});
    self.positionDropdown();
    self.$dropdown.css({visibility: 'visible'});
    self.trigger('dropdown_open', self.$dropdown);
  },

  /**
   * Closes the autocomplete dropdown menu.
   */
  close: function() {
    var self = this;
    var trigger = self.isOpen;

    if (self.settings.mode === 'single' && self.items.length) {
      self.hideInput();
    }

    self.isOpen = false;
    self.$dropdown.hide();
    self.setActiveOption(null);
    self.refreshState();

    if (trigger) self.trigger('dropdown_close', self.$dropdown);
  },

  /**
   * Calculates and applies the appropriate
   * position of the dropdown.
   */
  positionDropdown: function() {
    var $control = this.$control;
    var offset = this.settings.dropdownParent === 'body' ? $control.offset() : $control.position();
    offset.top += $control.outerHeight(true);

    this.$dropdown.css({
      width : $control.outerWidth(),
      top   : offset.top,
      left  : offset.left
    });
  },

  /**
   * Resets / clears all selected items
   * from the control.
   */
  clear: function() {
    var self = this;

    if (!self.items.length) return;
    self.$control.children(':not(input)').remove();
    self.items = [];
    self.setCaret(0);
    self.updatePlaceholder();
    self.updateOriginalInput();
    self.refreshState();
    self.showInput();
    self.trigger('clear');
  },

  /**
   * A helper method for inserting an element
   * at the current caret position.
   *
   * @param {object} $el
   */
  insertAtCaret: function($el) {
    var caret = Math.min(this.caretPos, this.items.length);
    if (caret === 0) {
      this.$control.prepend($el);
    } else {
      $(this.$control[0].childNodes[caret]).before($el);
    }
    this.setCaret(caret + 1);
  },

  /**
   * Removes the current selected item(s).
   *
   * @param {object} e (optional)
   * @returns {boolean}
   */
  deleteSelection: function(e) {
    var i, n, direction, selection, values, caret, option_select, $option_select, $tail;
    var self = this;

    direction = (e && e.keyCode === KEY_BACKSPACE) ? -1 : 1;
    selection = getSelection(self.$control_input[0]);

    if (self.$activeOption && !self.settings.hideSelected) {
      option_select = self.getAdjacentOption(self.$activeOption, -1).attr('data-value');
    }

    // determine items that will be removed
    values = [];

    if (self.$activeItems.length) {
      $tail = self.$control.children('.active:' + (direction > 0 ? 'last' : 'first'));
      caret = self.$control.children(':not(input)').index($tail);
      if (direction > 0) { caret++; }

      for (i = 0, n = self.$activeItems.length; i < n; i++) {
        values.push($(self.$activeItems[i]).attr('data-value'));
      }
      if (e) {
        e.preventDefault();
        e.stopPropagation();
      }
    } else if ((self.isFocused || self.settings.mode === 'single') && self.items.length) {
      if (direction < 0 && selection.start === 0 && selection.length === 0) {
        values.push(self.items[self.caretPos - 1]);
      } else if (direction > 0 && selection.start === self.$control_input.val().length) {
        values.push(self.items[self.caretPos]);
      }
    }

    // allow the callback to abort
    if (!values.length || (typeof self.settings.onDelete === 'function' && self.settings.onDelete.apply(self, [values]) === false)) {
      return false;
    }

    // perform removal
    if (typeof caret !== 'undefined') {
      self.setCaret(caret);
    }
    while (values.length) {
      self.removeItem(values.pop());
    }

    self.showInput();
    self.positionDropdown();
    self.refreshOptions(true);

    // select previous option
    if (option_select) {
      $option_select = self.getOption(option_select);
      if ($option_select.length) {
        self.setActiveOption($option_select);
      }
    }

    return true;
  },

  /**
   * Selects the previous / next item (depending
   * on the `direction` argument).
   *
   * > 0 - right
   * < 0 - left
   *
   * @param {int} direction
   * @param {object} e (optional)
   */
  advanceSelection: function(direction, e) {
    var tail, selection, idx, valueLength, cursorAtEdge, $tail;
    var self = this;

    if (direction === 0) return;
    if (self.rtl) direction *= -1;

    tail = direction > 0 ? 'last' : 'first';
    selection = getSelection(self.$control_input[0]);

    if (self.isFocused && !self.isInputHidden) {
      valueLength = self.$control_input.val().length;
      cursorAtEdge = direction < 0
        ? selection.start === 0 && selection.length === 0
        : selection.start === valueLength;

      if (cursorAtEdge && !valueLength) {
        self.advanceCaret(direction, e);
      }
    } else {
      $tail = self.$control.children('.active:' + tail);
      if ($tail.length) {
        idx = self.$control.children(':not(input)').index($tail);
        self.setActiveItem(null);
        self.setCaret(direction > 0 ? idx + 1 : idx);
      }
    }
  },

  /**
   * Moves the caret left / right.
   *
   * @param {int} direction
   * @param {object} e (optional)
   */
  advanceCaret: function(direction, e) {
    var self = this, fn, $adj;

    if (direction === 0) return;

    fn = direction > 0 ? 'next' : 'prev';
    if (self.isShiftDown) {
      $adj = self.$control_input[fn]();
      if ($adj.length) {
        self.hideInput();
        self.setActiveItem($adj);
        e && e.preventDefault();
      }
    } else {
      self.setCaret(self.caretPos + direction);
    }
  },

  /**
   * Moves the caret to the specified index.
   *
   * @param {int} i
   */
  setCaret: function(i) {
    var self = this;

    if (self.settings.mode === 'single') {
      i = self.items.length;
    } else {
      i = Math.max(0, Math.min(self.items.length, i));
    }

    // the input must be moved by leaving it in place and moving the
    // siblings, due to the fact that focus cannot be restored once lost
    // on mobile webkit devices
    var j, n, fn, $children, $child;
    $children = self.$control.children(':not(input)');
    for (j = 0, n = $children.length; j < n; j++) {
      $child = $($children[j]).detach();
      if (j <  i) {
        self.$control_input.before($child);
      } else {
        self.$control.append($child);
      }
    }

    self.caretPos = i;
  },

  /**
   * Disables user input on the control. Used while
   * items are being asynchronously created.
   */
  lock: function() {
    this.close();
    this.isLocked = true;
    this.refreshState();
  },

  /**
   * Re-enables user input on the control.
   */
  unlock: function() {
    this.isLocked = false;
    this.refreshState();
  },

  /**
   * Disables user input on the control completely.
   * While disabled, it cannot receive focus.
   */
  disable: function() {
    var self = this;
    self.$input.prop('disabled', true);
    self.isDisabled = true;
    self.lock();
  },

  /**
   * Enables the control so that it can respond
   * to focus and user input.
   */
  enable: function() {
    var self = this;
    self.$input.prop('disabled', false);
    self.isDisabled = false;
    self.unlock();
  },

  /**
   * Completely destroys the control and
   * unbinds all event listeners so that it can
   * be garbage collected.
   */
  destroy: function() {
    var self = this;
    var eventNS = self.eventNS;
    var revertSettings = self.revertSettings;

    self.trigger('destroy');
    self.off();
    self.$wrapper.remove();
    self.$dropdown.remove();

    self.$input
      .html('')
      .append(revertSettings.$children)
      .removeAttr('tabindex')
      .attr({tabindex: revertSettings.tabindex})
      .show();

    $(window).off(eventNS);
    $(document).off(eventNS);
    $(document.body).off(eventNS);

    delete self.$input[0].selectize;
  },

  /**
   * A helper method for rendering "item" and
   * "option" templates, given the data.
   *
   * @param {string} templateName
   * @param {object} data
   * @returns {string}
   */
  render: function(templateName, data) {
    var value, id, label;
    var html = '';
    var cache = false;
    var self = this;
    var regex_tag = /^[\t ]*<([a-z][a-z0-9\-_]*(?:\:[a-z][a-z0-9\-_]*)?)/i;

    if (templateName === 'option' || templateName === 'item') {
      value = hash_key(data[self.settings.valueField]);
      cache = !!value;
    }

    // pull markup from cache if it exists
    if (cache) {
      if (!isset(self.renderCache[templateName])) {
        self.renderCache[templateName] = {};
      }
      if (self.renderCache[templateName].hasOwnProperty(value)) {
        return self.renderCache[templateName][value];
      }
    }

    // render markup
    html = self.settings.render[templateName].apply(this, [data, escape_html]);

    // add mandatory attributes
    if (templateName === 'option' || templateName === 'option_create') {
      html = html.replace(regex_tag, '<$1 data-selectable');
    }
    if (templateName === 'optgroup') {
      id = data[self.settings.optgroupValueField] || '';
      html = html.replace(regex_tag, '<$1 data-group="' + escape_replace(escape_html(id)) + '"');
    }
    if (templateName === 'option' || templateName === 'item') {
      html = html.replace(regex_tag, '<$1 data-value="' + escape_replace(escape_html(value || '')) + '"');
    }

    // update cache
    if (cache) {
      self.renderCache[templateName][value] = html;
    }

    return html;
  }

});


Selectize.count = 0;
Selectize.defaults = {
  plugins: [],
  delimiter: ',',
  persist: true,
  diacritics: true,
  create: false,
  createOnBlur: false,
  highlight: true,
  openOnFocus: true,
  maxOptions: 1000,
  maxItems: null,
  hideSelected: null,
  addPrecedence: false,
  preload: false,

  scrollDuration: 60,
  loadThrottle: 300,

  dataAttr: 'data-data',
  optgroupField: 'optgroup',
  valueField: 'value',
  labelField: 'text',
  optgroupLabelField: 'label',
  optgroupValueField: 'value',
  optgroupOrder: null,

  sortField: '$order',
  searchField: ['text'],
  searchConjunction: 'and',

  mode: null,
  wrapperClass: 'selectize-control',
  inputClass: 'selectize-input',
  dropdownClass: 'selectize-dropdown',
  dropdownContentClass: 'selectize-dropdown-content',

  dropdownParent: null,

  /*
  load            : null, // function(query, callback) { ... }
  score           : null, // function(search) { ... }
  onInitialize    : null, // function() { ... }
  onChange        : null, // function(value) { ... }
  onItemAdd       : null, // function(value, $item) { ... }
  onItemRemove    : null, // function(value) { ... }
  onClear         : null, // function() { ... }
  onOptionAdd     : null, // function(value, data) { ... }
  onOptionRemove  : null, // function(value) { ... }
  onOptionClear   : null, // function() { ... }
  onDropdownOpen  : null, // function($dropdown) { ... }
  onDropdownClose : null, // function($dropdown) { ... }
  onType          : null, // function(str) { ... }
  onDelete        : null, // function(values) { ... }
  */

  render: {
    /*
    item: null,
    optgroup: null,
    optgroup_header: null,
    option: null,
    option_create: null
    */
  }
};

$.fn.selectize = function(settings_user) {
  var defaults             = $.fn.selectize.defaults;
  var settings             = $.extend({}, defaults, settings_user);
  var attr_data            = settings.dataAttr;
  var field_label          = settings.labelField;
  var field_value          = settings.valueField;
  var field_optgroup       = settings.optgroupField;
  var field_optgroup_label = settings.optgroupLabelField;
  var field_optgroup_value = settings.optgroupValueField;

  /**
   * Initializes selectize from a <input type="text"> element.
   *
   * @param {object} $input
   * @param {object} settings_element
   */
  var init_textbox = function($input, settings_element) {
    var i, n, values, option, value = $.trim($input.val() || '');
    if (!value.length) return;

    values = value.split(settings.delimiter);
    for (i = 0, n = values.length; i < n; i++) {
      option = {};
      option[field_label] = values[i];
      option[field_value] = values[i];

      settings_element.options[values[i]] = option;
    }

    settings_element.items = values;
  };

  /**
   * Initializes selectize from a <select> element.
   *
   * @param {object} $input
   * @param {object} settings_element
   */
  var init_select = function($input, settings_element) {
    var i, n, tagName, $children, order = 0;
    var options = settings_element.options;

    var readData = function($el) {
      var data = attr_data && $el.attr(attr_data);
      if (typeof data === 'string' && data.length) {
        return JSON.parse(data);
      }
      return null;
    };

    var addOption = function($option, group) {
      var value, option;

      $option = $($option);

      value = $option.attr('value') || '';
      if (!value.length) return;

      // if the option already exists, it's probably been
      // duplicated in another optgroup. in this case, push
      // the current group to the "optgroup" property on the
      // existing option so that it's rendered in both places.
      if (options.hasOwnProperty(value)) {
        if (group) {
          if (!options[value].optgroup) {
            options[value].optgroup = group;
          } else if (!$.isArray(options[value].optgroup)) {
            options[value].optgroup = [options[value].optgroup, group];
          } else {
            options[value].optgroup.push(group);
          }
        }
        return;
      }

      option                 = readData($option) || {};
      option[field_label]    = option[field_label] || $option.text();
      option[field_value]    = option[field_value] || value;
      option[field_optgroup] = option[field_optgroup] || group;

      option.$order = ++order;
      options[value] = option;

      if ($option.is(':selected')) {
        settings_element.items.push(value);
      }
    };

    var addGroup = function($optgroup) {
      var i, n, id, optgroup, $options;

      $optgroup = $($optgroup);
      id = $optgroup.attr('label');

      if (id) {
        optgroup = readData($optgroup) || {};
        optgroup[field_optgroup_label] = id;
        optgroup[field_optgroup_value] = id;
        settings_element.optgroups[id] = optgroup;
      }

      $options = $('option', $optgroup);
      for (i = 0, n = $options.length; i < n; i++) {
        addOption($options[i], id);
      }
    };

    settings_element.maxItems = $input.attr('multiple') ? null : 1;

    $children = $input.children();
    for (i = 0, n = $children.length; i < n; i++) {
      tagName = $children[i].tagName.toLowerCase();
      if (tagName === 'optgroup') {
        addGroup($children[i]);
      } else if (tagName === 'option') {
        addOption($children[i]);
      }
    }
  };

  return this.each(function() {
    if (this.selectize) return;

    var instance;
    var $input = $(this);
    var tag_name = this.tagName.toLowerCase();
    var settings_element = {
      'placeholder' : $input.children('option[value=""]').text() || $input.attr('placeholder'),
      'options'     : {},
      'optgroups'   : {},
      'items'       : []
    };

    if (tag_name === 'select') {
      init_select($input, settings_element);
    } else {
      init_textbox($input, settings_element);
    }

    instance = new Selectize($input, $.extend(true, {}, defaults, settings_element, settings_user));
    $input.data('selectize', instance);
    $input.addClass('selectized');
  });
};

$.fn.selectize.defaults = Selectize.defaults;

Selectize.define('drag_drop', function(options) {
  if (!$.fn.sortable) throw new Error('The "drag_drop" plugin requires jQuery UI "sortable".');
  if (this.settings.mode !== 'multi') return;
  var self = this;

  self.lock = (function() {
    var original = self.lock;
    return function() {
      var sortable = self.$control.data('sortable');
      if (sortable) sortable.disable();
      return original.apply(self, arguments);
    };
  })();

  self.unlock = (function() {
    var original = self.unlock;
    return function() {
      var sortable = self.$control.data('sortable');
      if (sortable) sortable.enable();
      return original.apply(self, arguments);
    };
  })();

  self.setup = (function() {
    var original = self.setup;
    return function() {
      original.apply(this, arguments);

      var $control = self.$control.sortable({
        items: '[data-value]',
        forcePlaceholderSize: true,
        disabled: self.isLocked,
        start: function(e, ui) {
          ui.placeholder.css('width', ui.helper.css('width'));
          $control.css({overflow: 'visible'});
        },
        stop: function() {
          $control.css({overflow: 'hidden'});
          var active = self.$activeItems ? self.$activeItems.slice() : null;
          var values = [];
          $control.children('[data-value]').each(function() {
            values.push($(this).attr('data-value'));
          });
          self.setValue(values);
          self.setActiveItem(active);
        }
      });
    };
  })();

});

Selectize.define('dropdown_header', function(options) {
  var self = this;

  options = $.extend({
    title         : 'Untitled',
    headerClass   : 'selectize-dropdown-header',
    titleRowClass : 'selectize-dropdown-header-title',
    labelClass    : 'selectize-dropdown-header-label',
    closeClass    : 'selectize-dropdown-header-close',

    html: function(data) {
      return (
        '<div class="' + data.headerClass + '">' +
          '<div class="' + data.titleRowClass + '">' +
            '<span class="' + data.labelClass + '">' + data.title + '</span>' +
            '<a href="javascript:void(0)" class="' + data.closeClass + '">&times;</a>' +
          '</div>' +
        '</div>'
      );
    }
  }, options);

  self.setup = (function() {
    var original = self.setup;
    return function() {
      original.apply(self, arguments);
      self.$dropdown_header = $(options.html(options));
      self.$dropdown.prepend(self.$dropdown_header);
    };
  })();

});

Selectize.define('optgroup_columns', function(options) {
  var self = this;

  options = $.extend({
    equalizeWidth  : true,
    equalizeHeight : true
  }, options);

  this.getAdjacentOption = function($option, direction) {
    var $options = $option.closest('[data-group]').find('[data-selectable]');
    var index    = $options.index($option) + direction;

    return index >= 0 && index < $options.length ? $options.eq(index) : $();
  };

  this.onKeyDown = (function() {
    var original = self.onKeyDown;
    return function(e) {
      var index, $option, $options, $optgroup;

      if (this.isOpen && (e.keyCode === KEY_LEFT || e.keyCode === KEY_RIGHT)) {
        self.ignoreHover = true;
        $optgroup = this.$activeOption.closest('[data-group]');
        index = $optgroup.find('[data-selectable]').index(this.$activeOption);

        if(e.keyCode === KEY_LEFT) {
          $optgroup = $optgroup.prev('[data-group]');
        } else {
          $optgroup = $optgroup.next('[data-group]');
        }

        $options = $optgroup.find('[data-selectable]');
        $option  = $options.eq(Math.min($options.length - 1, index));
        if ($option.length) {
          this.setActiveOption($option);
        }
        return;
      }

      return original.apply(this, arguments);
    };
  })();

  var equalizeSizes = function() {
    var i, n, height_max, width, width_last, width_parent, $optgroups;

    $optgroups = $('[data-group]', self.$dropdown_content);
    n = $optgroups.length;
    if (!n || !self.$dropdown_content.width()) return;

    if (options.equalizeHeight) {
      height_max = 0;
      for (i = 0; i < n; i++) {
        height_max = Math.max(height_max, $optgroups.eq(i).height());
      }
      $optgroups.css({height: height_max});
    }

    if (options.equalizeWidth) {
      width_parent = self.$dropdown_content.innerWidth();
      width = Math.round(width_parent / n);
      $optgroups.css({width: width});
      if (n > 1) {
        width_last = width_parent - width * (n - 1);
        $optgroups.eq(n - 1).css({width: width_last});
      }
    }
  };

  if (options.equalizeHeight || options.equalizeWidth) {
    hook.after(this, 'positionDropdown', equalizeSizes);
    hook.after(this, 'refreshOptions', equalizeSizes);
  }


});

Selectize.define('remove_button', function(options) {
  if (this.settings.mode === 'single') return;

  options = $.extend({
    label     : '&times;',
    title     : 'Remove',
    className : 'remove',
    append    : true
  }, options);

  var self = this;
  var html = '<a href="javascript:void(0)" class="' + options.className + '" tabindex="-1" title="' + escape_html(options.title) + '">' + options.label + '</a>';

  /**
   * Appends an element as a child (with raw HTML).
   *
   * @param {string} html_container
   * @param {string} html_element
   * @return {string}
   */
  var append = function(html_container, html_element) {
    var pos = html_container.search(/(<\/[^>]+>\s*)$/);
    return html_container.substring(0, pos) + html_element + html_container.substring(pos);
  };

  this.setup = (function() {
    var original = self.setup;
    return function() {
      // override the item rendering method to add the button to each
      if (options.append) {
        var render_item = self.settings.render.item;
        self.settings.render.item = function(data) {
          return append(render_item.apply(this, arguments), html);
        };
      }

      original.apply(this, arguments);

      // add event listener
      this.$control.on('click', '.' + options.className, function(e) {
        e.preventDefault();
        if (self.isLocked) return;

        var $item = $(e.target).parent();
        self.setActiveItem($item);
        if (self.deleteSelection()) {
          self.setCaret(self.items.length);
          self.trigger('optionActive', null);
        }
      });

    };
  })();

});

Selectize.define('restore_on_backspace', function(options) {
  var self = this;

  options.text = options.text || function(option) {
    return option[this.settings.labelField];
  };

  this.onKeyDown = (function(e) {
    var original = self.onKeyDown;
    return function(e) {
      var index, option;
      if (e.keyCode === KEY_BACKSPACE && this.$control_input.val() === '' && !this.$activeItems.length) {
        index = this.caretPos - 1;
        if (index >= 0 && index < this.items.length) {
          option = this.options[this.items[index]];
          if (this.deleteSelection(e)) {
            this.setTextboxValue(options.text.apply(this, [option]));
            this.refreshOptions(true);
          }
          e.preventDefault();
          return;
        }
      }
      return original.apply(this, arguments);
    };
  })();
});

module.exports = Selectize;
